public class BM2 {
    /*
    * 描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1→4→3→2→5→NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0<size≤10000<size≤1000，0<m≤n≤size0<m≤n≤size，链表中每个节点的值满足 ∣val∣≤1000∣val∣≤1000 */

    public static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {

        }
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n ){
            return head;
        }
        // 1.遍历链表找到反转起点
        ListNode cur = head;
        ListNode start = cur;
        ListNode startPre = null;
        for(int  i = 1 ; i < m; i++){
            startPre = start;
            start = start.next;
            cur = cur.next;
        }
        // 2.对m-n区间内部的链表翻转，头插法，注意不要断链
        ListNode newListHead = new ListNode(-1);
        newListHead.next = null;
        ListNode curNext;
        ListNode newTail = null;
        for(int i = m; i <= n;i++){
            curNext = cur.next;
            cur.next = newListHead.next;
            if(i == m){
                newTail = cur;
            }
            newListHead.next = cur;
            cur = curNext;
        }

        //3.连接三段链表
        assert newTail != null;
        newTail.next =cur;
        if (m != 1) {
            assert startPre != null;
            startPre.next = newListHead.next;
            return head;
        }else{
            return newListHead.next;
        }

    }

    // Function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // Define m and n for reversing the sublist from m to n
        int m = 2;
        int n = 5;

        // Reverse the sublist from m to n
        ListNode reversed = reverseBetween(head, m, n);

        // Print the reversed linked list
        printList(reversed);  // Output: 1 4 3 2 5
    }
}
